1. Field of the Invention
The present invention relates to route selection systems and, more specifically, to a system for automatically selecting an optimal route between a starting point and a destination designated on a map.
2. Description of the Background Art
Recently, with the progression of electronic technology, car navigation systems became popular with great speed. Some conventional car navigation systems are equipped with a route selection system so that an optimal route (e.g., shortest, fastest) between a starting point and a destination is automatically selected.
Applied in such conventional route selection system is exemplarily a method disclosed in Japanese Patent Laid-Open Publication No. 59-105113 (84-105113). This method makes use of Dijkstra method, for example, to determine an optimal route between a starting point and a destination utilizing data representing road connection. The theory of the Dijkstra method is found in xe2x80x9cData Structures and Algorithmsxe2x80x9d, written by A. V. Aho, et al., and translated by Yoshio Ono, Baifu-kan, 1990, pp. 179-183.
Another method for determining an optimal route is exemplarily a route search method disclosed in Japanese Patent Laid-Open Publication No. 4-204881 (92-204881). In this method, the route search is simultaneously made in a bi-directional manner, both a search from a starting point and a search from a destination. With such bi-directional search, searching time is shortened.
Still another method for determining an optimal route is disclosed in Japanese Patent Laid-Open Publication No. 4-372985 (92-372985) titled xe2x80x9cRecommended Route Guiding Devicexe2x80x9d, for example. The method is for calculating cost of right-turns and left-turns at intersections and adding the calculated cost to an evaluation value for an optimal route.
In such conventional methods, however, no consideration is given for stops at traffic lights and consequences to be caused thereby, including delay in a vehicle""s reaching its destination due to acceleration and deceleration before and after the stops. Therefore, any optimal route determined by such conventional methods cannot bring the vehicle to its destination within the estimated time.
Therefore, an object of the present invention is to provide a route selection method and system for searching for an optimal route while taking stops at traffic lights on the way into consideration.
In order to attain the object above, a first aspect of the present invention is directed to a route selection method for selecting an optimal route on a map, road network data representing an intersection and a road, and route selecting data including a traffic light flag to indicate whether the intersection has a traffic light or not are previously stored, the method comprising: a first step of determining, during a route search process for selecting an optimal route between a designated starting point and a destination, whether a target intersection has a traffic light by referring to the traffic light flag included in the route selecting data; and a second step of calculating, based on the determination made in the first step, a passage cost for passing the target intersection, wherein the passage cost calculated in the second step is based on to select the optimal route.
In the first aspect, the route selecting data including the traffic light flag which indicates presence or absence of traffic light at intersections is previously stored. In the second step, during the route search process based on the route selecting data, the passage cost is calculated depending on whether the target intersection has any traffic light. In this manner, the passage cost calculated in the second step can accordingly vary. Therefore, it becomes possible to find an optimal route under careful consideration for stops at traffic lights and consequences to be caused thereby, including delay in a vehicle""s reaching its destination due to acceleration and deceleration before and after the stops, for example
According to a second aspect, in the first aspect, in the second step, when the target intersection is determined as having the traffic light in the first step, a traffic light cost relevant to a waiting time due to the traffic light is calculated, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
In the second aspect, the traffic light cost is calculated only when the target intersection has any traffic light. In this manner, in the route search process, it becomes possible to find an optimal route under careful consideration for a waiting time due to traffic lights and consequences to be caused thereby.
According to a third aspect, in the first aspect, the route selecting data further includes road type information for specifying a road by type, and in the second step, when the target intersection is determined as having the traffic light in the first step, the road type information for a road connected to the target intersection is referred to for calculating the traffic light cost relevant to the waiting time due to the traffic light, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
In the third aspect, the traffic light cost is calculated based on a road type of roads connected to the intersection. In this manner, the traffic light cost thus calculated can vary depending on whether the road leading to the intersection has a higher priority over the others. Therefore, in the route search process, it becomes possible to find an optimal route in a manner reflecting any influence caused by a waiting time at intersections, for example.
According to a fourth aspect, in the first aspect, the route selection data further includes road width information for specifying a road by width, in the second step, when the target intersection is determined as having the traffic light in the first step, the road width information for a road connected to the target intersection is referred to for calculating the traffic light cost relevant to the waiting time due to the traffic light, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
According to a fifth aspect, in the first aspect, the route selection data further includes lane information for specifying a road by the number of lanes, in the second step, when the target intersection is determined as having the traffic light in the first step, the lane information for a road connected to the target intersection is referred to for calculating the traffic light cost relevant to the waiting time due to the traffic light, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
In the fourth and fifth aspects, the traffic light cost is calculated by referring to the width or the number of lanes of a road connected to an intersection. In this manner, the traffic light cost thus calculated can vary depending on whether the road leading to the intersection has a higher priority over the others. Further, in the fourth and fifth aspects, the roads connected to the intersection are compared with one another in width (or the number of lanes). In this manner, the traffic light cost thus calculated can vary depending on whether the road leading to the intersection has a higher priority over the others. Therefore, in the route search process, it becomes possible to find an optimal route in a manner reflecting any influence caused by a waiting time at intersections, for example.
According to a sixth aspect, in the first aspect, the route selecting data includes a predetermined reference waiting time cost, and a ratio of waiting time on the load leading to an intersection having a traffic light to the reference waiting time, and in the second step, when the target intersection is determined as having the traffic light in the first step, the reference waiting time cost and the waiting time ratio on the road leading to the target intersection are referred to for calculating the traffic light cost relevant to the waiting time due to the traffic light, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
In the sixth aspect, the traffic light cost is calculated based on the reference waiting time cost and the ratio of waiting time for every road leading to the intersection. In this manner, the traffic light cost thus calculated can vary depending on the roads leading to the intersection. Therefore, it becomes possible to find an optimal route in a manner accurately reflecting any influence caused by a waiting time at intersections, for example.
According to a seventh aspect, in the sixth aspect, the reference waiting time cost is an averaged value for waiting times at every intersection having a traffic light.
In the seventh aspect, the reference waiting time is taken through actual measurements at intersections. Therefore, the traffic light cost can be calculated with higher accuracy.
According to an eighth aspect, in the sixth aspect, the route selecting data does not necessarily include the waiting time ratio with respect to the reference waiting time cost for every road leading to the intersection having the traffic light, and in the second step, even if the ratio for a road leading to the target intersection is not included, the ratio for other road leading thereto is referred to for calculating the traffic light cost for the target intersection.
Generally, a plurality of roads leading to an intersection having traffic lights is found plural. In the eighth aspect, the route selecting data does not necessarily include the waiting time ratio for every road leading to the intersection, thereby allowing the data amount of the route selecting data reduced. Accordingly, for any application (e.g., automotive application) naturally restricted in capacity of storage, reduction in the data amount is highly advantageous.
According to a ninth aspect, in the first aspect, the road network data represents a road network by a combination of node and link, and several intersections are represented by several nodes and at least one link, the route selecting data includes an intersection flag which indicates whether the link representing the road network is an intra-intersection link or an extra-intersection link, and in the second step, when the target intersection is determined as having the traffic light in the first step, the intersection flag is referred to for calculating the traffic light cost relevant to the waiting time at the target intersection, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
In the ninth aspect, intersections in the road network data may be represented by several nodes and at least one link. Further, the link representing the road network is classified, by the intersection flag, into an intra-intersection link and an extra-intersection link. By utilizing the intersection flag, the traffic light cost can be prevented from being calculated for more than once for the intersection represented by several nodes.
According to a tenth aspect, in the ninth aspect, in the second step, the intersection flag is referred to for determining whether a link representing the road leading to the target intersection is the intra-intersection link or the extra-intersection link, and only when the link representing the road leading to the target intersection is determined as being the extra-intersection link, the traffic light cost is calculated for the traffic light at the target intersection.
According to an eleventh aspect, in the ninth aspect, in the second step, the intersection flag is referred to for determining whether a not-searched link connected to a node representing the target intersection is the intra-intersection link or the extra-intersection link, and only when the not-searched link is determined as being the extra-intersection link, the traffic light cost is calculated for the traffic light at the target intersection.
In the tenth or eleventh aspect, the traffic light cost is calculated only when the intersection flag of the link leading to the target intersection is the extra- or intra-intersection link. In this manner, the traffic light cost can be prevented from being calculated more than once for the intersection represented by several nodes.
According to a twelfth aspect, in the ninth aspect, in a case where the route search process is done in a bi-directional manner started from the designated starting point and from the designated destination, in the second step, for the route search started from the designated destination, the intersection flag is referred to for determining whether a not-searched link connected to a node representing the target intersection is the intra-intersection link or the extra-intersection link, and only when the not-searched link is determined as being the extra-intersection link, the traffic light cost is calculated for the traffic light at the target intersection.
According to a thirteenth aspect, in the ninth aspect, in a case where the route search process is done in a bi-directional manner started from the designated starting point and from the designated destination, in the second step, for the route search started from the designated destination, the intersection flag is referred to for determining whether an accessible link to a node representing the target intersection is the intra-intersection link or the extra-intersection link, and only when the accessible link is determined as being the extra-intersection link, the traffic light cost is calculated for the traffic light at the target intersection.
In the twelfth or thirteenth aspect, in the route search made either from the starting point or the destination, the traffic light cost is calculated for the traffic light at the intersection only when the not-searched link is determined as being the intra- or extra-intersection link for the intersection. Accordingly, the traffic light cost is calculated only once for the intersection represented by several nodes. In detail, the traffic light cost can be prevented from not being calculated or calculated for more than once. Further, under such route search method, even if the intersection is represented by several nodes, in the route search from the destination and that from the staring point, the same node is used for calculating the traffic light cost for the intersection. As a result, the passage cost calculated can be accurate.
According to a fourteenth aspect, in the first aspect, the route selecting data includes a linkage table in which a set of intersections each having a traffic light working in a synchronous manner is stored as a linkage, and in the second step, when the target intersection is determined as having the traffic light in the first step, the linkage table is referred to for calculating the traffic light cost relevant to the waiting time due to the traffic light, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
Herein, it is assumed that traffic lights on a road are working in a synchronous manner. On such road, once a first traffic light turns on green, vehicles can smoothly pass through several following traffic lights without stopping. If this is the case, it is practically better not to calculate the traffic light cost for every intersection which has been passed. By taking this into consideration, in the fourteenth aspect, the linkage table has sets of nodes working in a synchronous manner recorded as a linkage. Utilizing such linkage table, the traffic light cost is calculated for the intersections in the second step. The traffic light cost thus calculated can more preferably correspond to such synchronization of the traffic lights. Therefore, the route search can be carried out in a correct manner realistic for actual traffic by, for example, calculating the traffic light cost only for an intersection with a first traffic light in a section where traffic lights are synchronously working.
According to a fifteenth aspect, in the fourteenth aspect, in the second step, when the target intersection is determined as having the traffic light in the first step, the linkage table is referred to for comparing a linkage of a previous intersection with a linkage of the target intersection, based on a result of the comparison, the traffic light cost relevant to the waiting time due to the traffic light at the target intersection is calculated, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
According to a sixteenth aspect, in the fifteenth aspect, in the second step, when the target intersection is determined as having the traffic light in the first step, the linkage table is referred to for determining whether an intersection one before and the target intersection belong to the same linkage, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
According to a seventeenth aspect, in the fifteenth aspect, in the second step, when the target intersection is determined as having the traffic light in the first step, the linkage table is referred to for comparing an intersection two before and the target intersection belong to the same linkage, when the linkage of the intersection two before is different from the linkage of the target intersection, the traffic light cost relevant to the waiting time due to the traffic light at the intersection is calculated, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
In the fifteenth to seventeenth aspects, comparison is made between the previous intersection (one or two before) and the target intersection in linkage to see if they are equal. Based on a result obtained thereby, the traffic light cost is calculated. In this manner, the traffic light cost is calculated in a more preferable manner corresponding to the synchronization of traffic lights.
Herein, it is assumed that a vehicle makes a right turn and enters to a linkage having traffic lights synchronously working. In such case, a traffic light at the first intersection appearing after the vehicle""s making of the right turn is often on red. By taking this into consideration, in the seventeenth aspect, comparison is made between an intersection two before and a target intersection in linkage to see if they are equal. Based on the comparison thus made, the traffic light cost is calculated. In this manner, the calculated traffic light cost can more preferably corresponds to traffic lights"" working on actual roads.
According to an eighteenth aspect, in the fifteenth aspect, in the second step, when the target intersection is determined as having the traffic light in the first step, the linkage table is referred to for determining whether the previous intersection and the target intersection belong to the same linkage, immediately after the previous intersection and the target intersection are determined as belonging to the same linkage for a predetermined number of times in a row, the traffic light cost relevant to the waiting time due to the traffic light at the target intersection is calculated, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
According to a nineteenth aspect, in the fifteenth aspect, in the second step, when the target intersection is determined as having the traffic light in the first step, the linkage table is referred to for determining whether the previous intersection and the target intersection belong to the same linkage, immediately after the previous intersection and the target intersection are determined as belonging to the same linkage for a predetermined amount of time, the traffic light cost relevant to the waiting time due to the traffic light at the target intersection is calculated, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
In a section where traffic lights are synchronously working, vehicles rarely passes through the section without stopping at intersections. Therefore, the traffic light cost is calculated, in the eighteenth aspect, immediately after the previous intersection and the target intersection are determined as belonging to the same linkage for a predetermined number of times in a row, and in the nineteenth aspect, immediately after the previous intersection and the target intersection are determined as belonging to the same linkage for a predetermined amount of time. In this manner, when a vehicle goes in a section where traffic lights are synchronously working, the traffic light cost is calculated after a certain length of time of driving. Accordingly, the calculated traffic light cost can more preferably corresponds to traffic lights"" working on actual roads.
According to a twentieth aspect, in the fourteenth aspect, the linkage table has a set of intersections each having a traffic light working in a synchronous manner recorded as a linkage, and in the second step, when the target intersection is determined as having the traffic light in the first step, a time for passing the target intersection is estimated, the linkage table is referred to for determining the linkage to which the target intersection belongs at the estimated time, the linkage of the target intersection is compared with the linkage of the previous intersection, and based on the result of the comparison, the traffic light cost relevant to the waiting time due to the traffic light at the target intersection is calculated, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
In an actual road network, a combination of traffic lights which work synchronously and which may change depending on a time range exists. Therefore, in the twentieth aspect, the linkage table has sets of intersections each having a traffic light working in a synchronous manner are stored. In the second step, such linkage table is referred to for calculating the traffic light cost, thereby rendering the traffic light cost thus calculated more realistically preferable.
A twenty-first aspect of the present invention is directed to a route selection system for selecting an optimal route on a map, comprising: a route selecting data storage for storing road network data representing an intersection and a road, and route selecting data including a traffic light flag which indicates if the intersection has a traffic light or not; an optimal route searcher for carrying out a route search process for selecting an optimal route between a starting point and a destination based on the route selecting data stored in the route selecting data storage; and a traffic light cost calculator which operates when the optimal route searcher is looking for the optimal route, wherein, in the route search process, the optimal route searcher refers to the traffic light flag in the route selecting data stored in the route selecting data storage to determine whether a target intersection has a traffic light, when the optimal route searcher determines that the target intersection has the traffic light, the traffic light cost calculator calculates a traffic light cost relevant to a waiting time due to the traffic light, and based on the traffic light cost calculated by the traffic light cost calculator, the optimal route searcher calculates a passage cost relevant to a time for passing the target intersection.
According to a twenty-second aspect, in the twenty-first aspect, the route selecting data further includes a predetermined reference waiting time cost, and a ratio of waiting time on the roads leading to an intersection having a traffic light to the reference waiting time, and when the optimal route searcher determines that the target intersection has the traffic light, the traffic light cost calculator calculates the traffic light cost relevant to the waiting time due to the traffic light based on the reference waiting time cost and the waiting time ratio at the intersection.
According to a twenty-third aspect, in the twenty-second aspect, the route selecting data includes the waiting time ratio to the reference waiting time cost for some of the roads leading to the intersection having the traffic light. Even if no waiting time ratio is provided for a road leading to the target intersection, the traffic light cost calculator calculates the traffic light cost for the target intersection based on a waiting time ratio provided for another road leading thereto.
According to a twenty-fourth aspect, in the twenty-first aspect, the road network data represents a road network by a combination of node and link, and the intersection appeared therein may be represented by several nodes and at least one link, the route selecting data further includes an intersection flag which indicates whether the link representing the road network is an intra-intersection link or an extra-intersection link, and the traffic light cost calculator refers to the intersection flag to calculate the traffic light cost relevant to the waiting time due to the traffic light at the target intersection.
According to a twenty-fifth aspect, in the twenty-first aspect, the route selecting data further includes a linkage table in which a set of intersections each having a traffic light working in a synchronous manner is recorded as a linkage, and the traffic light cost calculator refers to the linkage table to calculate the traffic light cost relevant to the waiting time due to the traffic light at the target intersection.
According to a twenty-sixth aspect, in the twenty-fifth aspect, the traffic light cost calculator refers to the linkage table, when the optimal route searcher determines that the target intersection has the traffic light, to determine whether an intersection two before and the target intersection belong to the same linkage, and calculates, when the linkage of the intersection two before is different from the linkage of the target intersection, the traffic light cost relevant to the waiting time due to the traffic light at the target intersection.
According to a twenty-seventh aspect, in the twenty-sixth aspect, the linkage table has a set of intersections each having a traffic light working in a synchronous manner stored as a linkage on a time range basis, and the traffic light cost calculator estimates a time to pass the target intersection, and refers to the linkage table having a linkage stored on the time range basis for determining to which linkage the target intersection belongs at the estimated time, and compares the linkage of the previous intersection and the linkage of the target intersection, and based on a result of the comparison, calculates the traffic light cost relevant to the waiting time due to the traffic light at the target intersection.
A twenty-eighth aspect of the present invention is directed to a recording medium on which a program is recorded for realizing, on a computer device, a process for selecting an optimal route on a map, the recording medium previously storing road network data representing an intersection and a road, and route selecting data including a traffic light flag which indicates if the intersection has a traffic light, the program comprising: a first step of determining, during a route search process for selecting an optimal route between a designated starting point and a destination, whether a target intersection has a traffic light by referring to the traffic light flag included in the route selecting data; and a second step of calculating, based on the determination made in the first step, a passage cost for passing the target intersection, wherein based on the passage cost calculated in the second step, the optimal route is selected.
According to a twenty-ninth aspect, in the twenty-eighth aspect, in the second step, when the target intersection is determined as having the traffic light in the first step, a traffic light cost relevant to a waiting time at the traffic light at the target intersection is calculated, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
According to a thirtieth aspect, in the twenty-eighth aspect, the route selecting data includes a predetermined reference waiting time cost, and a ratio of waiting time on the roads leading to an intersection having a traffic light to the reference waiting time, and in the second step, when the target intersection is determined as having the traffic light in the first step, the reference waiting time cost and the waiting time ratio on the road leading to the target intersection are referred to for calculating the traffic light cost relevant to the waiting time due to the traffic light, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
According to a thirty-first aspect, in the twenty-eighth aspect, the road network data represents a road network by a combination of node and link, and the intersection appeared therein may be represented by several nodes and at least one link, the route selecting data includes an intersection flag which indicates whether the link representing the road network is an intra-intersection link or an extra-intersection link, and in the second step, when the target intersection is determined as having the traffic light in the first step, the intersection flag is referred to for calculating the traffic light cost relevant to the waiting time at the target intersection, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
According to a thirty-second aspect, in the twenty-eighth aspect, the route selecting data includes a linkage table in which a set of intersections each having a traffic light working in a synchronous manner is stored as a linkage, and in the second step, when the target intersection is determined as having the traffic light in the first step, the linkage table is referred to for calculating the traffic light cost relevant to the waiting time due to the traffic light, and based on the calculated traffic light cost, the passage cost is calculated for the target intersection.
These and other objects, features, aspects and advantages of the present invention will become more apparent from the following detailed description of the present invention when taken in conjunction with the accompanying drawings.